A digital transmission system conveys information using a physical carver such as cable, optical fibre or propagation on a radio channel, satellite or otherwise. Such a physical medium will be referred to as a channel. Generally, such a system comprises in particular, on the sending side, a device referred to as a channel coder and, on the receiving side, a corresponding decoding device.
The channel coding device has a so-called error correcting coding function. The error correcting coding function consists of generating redundant information on sending which, during decoding at the destination, will make it possible to reconstitute the useful information transmitted, using the information arriving at its destination, referred to as the received information, affected by the disturbance occurring on the channel, notably of the noise, attenuation and interference type. A digital transmission method using such a channel coding associated with a corresponding destination decoding is referred to as a transmission method of the error correcting coding type.
For example, the coding operation takes place at the level of the bit. This operation associates with a binary sequence of useful information a binary sequence of corresponding coded information. This binary sequence of coded information is referred to as the code word when the size of the binary sequences of useful information is fixed. The binary sequence of coded information is of greater size than the binary sequence of useful information so as to introduce redundancy. Because of this redundancy, only certain coded information sequences, in accordance with the coding law, are possible. If received information sequences to be decoded are different from these possible sequences, it is because they correspond to information impaired by the channel. The role of the decoding method will therefore be to reconstitute the useful information as well as possible from the received information sequence, knowing the coding law used. It is known how to decode the most simple codes in optimum fashion, that is to say by finding, amongst the possible sequences, the most likely sequence. For the more complex codes such as turbo codes, the limiting factor is in general the complexity of the decoder.
The performance of a transmission with error correcting coding is generally measured in terms of rate of binary errors or packets for a given signal to noise ratio Eb/No, where Eb is the energy per information bit and No is the power spectral density of the noise. A code is referred to as more or less efficient depending on whether its use affords a higher or lower error rate for a given ratio Eb/No and for a given decoding complexity.
The efficiency of the code is the number of useful information bits per coded information bit.
Known error correcting codes are block codes. Block coding consists of associating with each block of k information bits a block of n bits (n>k) therefore containing (n−k) redundant bits. The block of n bits is obtained by multiplying the block of k useful bits by a matrix with k rows and n columns referred to as a generating matrix for the code. When, by permutation, the generating matrix is written in a form such that it reveals the identity matrix, so that, in the block of n bits, the k information bits and the n−k redundancy bits are separated, the code is said to be systematic. The efficiency of the code is equal to k/n. The decoding device detects the errors and corrects them by means of the minimum Hamming distance. Such error correcting codes well known in the art are for example Hamming codes, BCH codes and Reed-Solomon codes.
Effecting an error correcting coding by means of one or more convolutional codings is also well known. Their operating principle consists of coding a block of k binary elements present at the input of the coder as a block of n binary elements also taking account of m blocks preceding the block present in the input, using a device with a register of the shift register type. The output of the convolutional coder consists of n coded binary elements generated by the convolution product of the k binary elements present at the input with the response of the coder defined by n generator polynomials. The efficiency of the code is equal to k/n. The decoding device reconstructs the original data, for example by means of a decoding of the sequential type, a decoding according to the most likely symbol, or a decoding according to the most likely sequence, as described, for example, in the document “Digital Communications”, by J. G. Proakis, which appeared in 1995 in a publication by MacGraw-Hill. For example, the Viterbi algorithm provides an optimum decoding according to the most likely sequence.
According to a variant of this type of code, coding is not effected by directly taking into account a series of m useful information items preceding the information to be coded, but by using a series of m auxiliary information items, stored in a device of the shift register type, each obtained by the mathematical combination of a useful information item and m auxiliary information items calculated previously. Such a convolutional code is said to be recursive. When, in addition, the useful information appears as it is amongst the n outputs of the coder alongside (n−1) coded information items or redundant information items, the resulting code is referred to as a recursive systematic convolutional code, or RSC code.
Associating different coders in order to increase the performance of the coding is also known. For example, the data coded by a first coder can supply a second coder. Decoding takes place symmetrically, commencing with the second code.
A high-performance type of combination of coders has been proposed, as described notably in the document “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-codes” by C. Berrou, A. Glavieux and P. Thitimajshima, which appeared in ICC-1993, Conference Proceedings, on pages 1064–1070. This type of combination of coders has given rise to a family of coding schemes known in the art as turbo codes. The term turbo codes will be given to error correcting codes based on the combination, referred to as concatenation, of several simple codes, referred to as elementary codes, with the intervention of permutation operations, referred to as interleavings, which modify the order of taking into account of the data by each of the simple codes. For example, one type of conventional interleaving, referred to as uniform interleaving, is obtained by means of an interleaving matrix in which the source data are introduced row by row and retrieved column by column. In general, in order to improve the performance, the turbo codes use non-uniform interleavings. Elementary codes means codes with an efficiency greater than or equal to 1, of the type described above. It may, for example, be a case of recursive systematic convolutional codes for convolutional turbo codes, Hamming block codes or BCH for block turbo codes. Different types of concatenation can be envisaged. In parallel concatenation, the same information is coded for each coder separately after having been interleaved. In serial concatenation, the output of each coder is coded by the following coder after having been interleaved. The term dimension of the turbo code refers to the number of elementary coders used for implementing this turbo code. A well known turbo coding scheme consists of a parallel concatenation of elementary codes of the recursive systematic convolutional (RSC) code, type. This turbo code is referred to by the term PCCC. Examples of turbo codes with serial concatenation are SCCCs which use elementary codes of the convolutional code type and block turbo codes which use elementary codes of the block code type.
Information coded by a turbo code can be decoded by an iterative method referred to as turbo decoding. An example of turbo decoding is given in the aforementioned document “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-codes”, by C. Berrou, A. Glavieux and P. Thitimajshima, which appeared in ICC-1993, Conference Proceedings, on pages 1064–1070. In this example, it is a case of the turbo decoding of a turbo code with parallel concatenation. There are combined several elementary decoders with weighted inputs and outputs each corresponding to an elementary coder of the coding device. The weighted inputs and outputs are effected in terms of probabilities, likelihood ratios or log likelihood ratios. The weighted inputs and outputs are generally associated with each of the m-ary symbols at the input and output of the elementary coders, that is to say, for example, with bits if binary coders are used as elementary coders. The decoders work one after the other in the case of a type of turbo decoding referred to as serial turbo decoding, or simultaneously in a type of turbo decoding known as parallel turbo decoding. Intermediate concatenation schemes can also be envisaged. Interleavers and deinterleavers act as a function of the interleavings carried out at coding. They enable each decoder to take into account an information item which is presented in the same order as at the output and input of the corresponding coder. Each elementary decoder uses the available information which corresponds to the information at the input and output of the corresponding elementary coder. The available information used by the elementary decoder, referred to as a priori information, consists of an output of the step preceding the channel decoding, namely, in general, a demodulation step, and an information item generated by one or more previous elementary decoding steps. By virtue of this a priori information and knowing the coding law of the corresponding elementary coder, the elementary decoder generates an a posteriori information item which is an estimation of the greatest reliability of the input information. The additional information compared with the input information is referred to as extrinsic information. This extrinsic information is transmitted to the following elementary decoder, which will use it as a priori information after interleaving or deinterleaving, and possible combination. Each elementary decoding step therefore benefits at the input from a priori information whose quality is increased by the elementary decodings carried out during the previous elementary decoding steps. This extrinsic information depends on the redundant information introduced by the corresponding coder. The method is iterative in that the extrinsic information calculated by the last decoder or decoders in the series is propagated back to the first decoder or decoders in the series. The exchange of extrinsic information takes place between elementary decoders within the same step, and from this step to the following step. Each new step therefore increases the reliability of the information generated at an output. After a certain number of iterations, the decoding process stagnates, whether or not it has converged towards the solution. A thresholding is applied in order to generate the decoded information.
Naturally, the term turbo decoding encompasses various concatenation schemes which can be envisaged, depending for example on the type of turbo coding implemented. For example, in the turbo decoding corresponding to a turbo code with serial concatenation, the elementary decoders being associated in the reverse order of the elementary coders, each elementary decoder receives two a priori weighted information items corresponding one to the output information from the corresponding elementary coder and the other to the input information of the corresponding elementary coder. This elementary decoder produces two a posteriori weighted information items, one corresponding to the output of the corresponding elementary coder, and which therefore becomes, at the time of a following iteration, after corresponding interleaving, the a priori input of a preceding elementary decoder, and the other corresponding to the input of the corresponding elementary coder, which therefore becomes, in the same iteration, after corresponding deinterleaving, the a priori input of a following elementary, decoder.
Whatever the case, the extrinsic information can always be defined as the additional information given by an elementary decoding associated with an elementary coding with respect to an a priori information item, acting at the input of the elementary decoding.
In addition, it is possible to use various types of algorithm for elementary decoders with weighted inputs and outputs. Elementary decoders use, for example, MAP, LogMAP and MaxLogMAP algorithms, also referred to as APP, LogAPP and MaxLogAPP, which all derive from the calculation of a posteriori probabilities knowing a priori probabilities. Reference can be made, for a description of such decoding algorithms, for example, to the article “Optimal and sub-optimal maximum a posteriori algorithms suitable for turbo decoding” by P. Robertson, P. Hoeher and E. Villebrun, which appeared in European Trans. on Telecommun., vol. 8, March–April 1997, pages 119–125. It is also possible to use algorithms of the Viterbi algorithm type modified to associate, with each decision, a possible to use the SOVA (Soft Output Viterbi Algorithm). For block turbo codes, it is possible to use a Chase algorithm, as described in the article “A very low complexity block turbo decoder for product codes” by R. Pyndiah, P. Combelles and P. Adde, which appeared in IEEE Globecom 1996, pages 101 to 105.
It is also known that the efficiency of a code can be increased by a puncturing operation which consists of transmitting only certain bits of an information sequence, as described, for example, in the article “Rate-Compatible Punctured Convolutional (RCPC) codes and their application”, by J. Hagenauer, which appeared in IEEE Trans., Vol. COM-36.4, 1988, pages 389–400 or in the article “New Rate Compatible Punctured Convolutional Codes for Viterbi Decoding”, by L. H. C. Lee, which appeared in IEEE Trans., Vol. COM-42.2, 1994, pages 3073–3079. These non-transmitted bits are in general redundant information bits. This puncturing operation occurs at the sending level, after the coding operation. At the destination, a reciprocal operation of depuncturing is carried out before the decoding operation. The puncturing and depuncturing operations are defined by a puncturing matrix or diagram. The puncturing of redundant information bits reduces the correction capability of the code and increases its efficiency.
The error correcting codes of the family of turbo codes according to the state of the art described above make it possible to obtain a very high performance error correction whilst preserving sufficiently high efficiencies and allowing decoding operations of low complexity compared with the complexity of the code. Turbo decoding, sub-optimal in its principle, has a performance close to that of the optimal decoder and an appreciably lower complexity, since it is of the order of that of the decoding of the elementary codes.
However, the complexity of the turbo decoding and parameters such as the turbo decoding time or the energy consumption for turbo decoding can increase with a number of iterations of the turbo decoding procedure. There is then posed the problem of interruption of the turbo decoding. Naturally, a predetermined number of turbo decoding iterations can be fixed. However, it may happen then that this predetermined number of iterations is either insufficient, then not making it possible to achieve a satisfactory error correction, or too high, meaning that a certain number of iterations are unnecessary. This way of proceeding then takes place either to the detriment of the transmission performance, measured for example in terms of bit error rate, or to the detriment of the transmission conditions such as the complexity of the turbo decoding, the turbo decoding time or the consumption of energy for turbo decoding.
Generally, a maximum number of iterations is fixed corresponding to an acceptable complexity and/or maximum decoding time, and a stop criterion is used for interrupting the decoding process if this seems to have given rise to a convergence towards the useful information before the maximum number of iterations. Convergence can be detected in different ways. For example, an error detection code of the CRC (Cyclic Redundancy Check) type maybe used. If, during the decoding of an information sequence, the calculation of the error detecting code indicates that there are no more errors, the iterative decoding for the sequence is interrupted. A drawback of this method stems from the fact that an error detecting code must be introduced on transmission, which reduces the overall efficiency of the channel coder.
There have also been proposed criteria for the interruption of the turbo decoding based on a comparison of information sequences at the output of at least two successive elementary decoders. Such interruption criteria are described, for example, in an article by M. Moher whose title is “Decoding via Cross-Entropy Minimization”, which appeared in “Proceedings of Globecom'93, IEEE Global Telecommunications Conference”, vol. 2, pages 809–813, or in an article by R. Y. Shao, S. Lin and M. P. C. Fossorier entitled “Two simple stopping criteria for turbo-decoding”, which appeared in “IEEE Transactions on Comm.”, vol 47, No. 8, August 1999, pages 1117–1120. The use of such criteria for interruption of the turbo decoding is based notably on the fact that a stagnation of the outputs of the elementary decoders during the iterative decoding of a sequence of information indicates that additional decoding iterations will not further reduce the number of errors occurring on this information sequence.
Nevertheless, this type of turbo decoding interruption criterion poses two types of problem.
First of all, though the principle on which this criterion is based makes it possible, in a relatively simple manner, to control the stoppage of the decoding processing, it does not give any indication of the quality of the decoded information sequences, that is to say on the number of errors which they contain with respect to the useful information nor even on the possible presence of residual errors.
Next, the use of this type of interruption criterion assumes the storage of an information sequence issuing from a step which precedes the decoding step under consideration in order to carry out the comparison. Generally, it is even necessary to store several sequences issuing from steps preceding the step under consideration so that the functioning of the criterion is satisfactory.
Finally, since this interruption criterion is based on a stagnation of the outputs of successive elementary decoders, it detects the convergence of the decoding method at least one step after it has effectively converged. In the case of a convergence at the penultimate step of elementary decoding, the last step effected is therefore unnecessary.